[프로그래머스] 260516 계획
NOTE
요약 대기업 코딩테스트 대비 알고리즘 체화 커리큘럼. Phase 1(핵심 5대 알고리즘: 완전탐색·구현·해시/투포인터·이분탐색·DP)과 Phase 2(심화 특수 유형: 상태 환원 백트래킹/TSP·비트마스킹·2차원 누적합·트라이)로 구성. 체크박스는 진행 상태 표시.
📋 배경 메모
말씀하신 ‘웹환원순회’는 아마도 컴퓨터 공학의 아주 유명한 고전 알고리즘인 외판원 순회(TSP, Traveling Salesperson Problem)를 떠올리신 것 같습니다! 발음이 비슷해서 흔히 헷갈리기 쉬운 용어입니다.
외판원 순회(TSP)는 “여러 도시를 한 번씩만 방문하고 다시 출발점으로 돌아오는 최소 비용 경로”를 찾는 문제입니다. 이 문제는 앞서 말씀드린 DFS(상태 환원 백트래킹)와 비트마스킹이 완벽하게 결합되어야만 풀 수 있는 최상위권 단골 출제 유형입니다.
이러한 특수 알고리즘들이 낯설게 느껴지시는 것은 당연합니다. 하지만 대규모 트래픽을 다루는 IT 기업에서는 효율성 테스트의 변별력을 높이기 위해 이 유형들을 ‘킬러 문항’으로 반드시 출제합니다.
실제 결제나 정산 시스템에서 데이터 정합성을 맞추기 위해 트랜잭션을 롤백(Rollback)하는 것처럼 상태 환원 백트래킹을 사용하고, DB의 검색 속도를 높이기 위해 인덱싱을 타는 원리가 곧 트라이(Trie) 자료구조와 맞닿아 있습니다. 따라서 커리큘럼의 ‘심화(Phase 2)’ 단계로 추가해 두고, 기본기 5가지를 체화한 뒤에 도전하시는 것을 강력히 추천합니다.
🎯 대기업 코딩테스트 대비 알고리즘 체화 커리큘럼 (통합본)
💡 학습 가이드
- Phase 1 (핵심 5대장): 코딩테스트 합격의 80%를 결정짓는 필수 유형. 초급➔중급➔고급 순으로 완벽히 체화합니다.
- Phase 2 (심화 특수 유형): 네카라쿠배 등 대기업의 ‘킬러 문항(효율성 테스트)‘을 뚫어내기 위한 변별력 알고리즘입니다. Phase 1이 숙달된 후 진입합니다.
🟢 Phase 1: 핵심 5대 알고리즘
1. 🌐 완전 탐색 (BFS / DFS)
- 🟢 [초급] 타겟 넘버 (Lv.2) : DFS 상태 공간 탐색 기본
- 🟢 [초급] 게임 맵 최단거리 (Lv.2) : 2D 격자 BFS 최단 거리 기본
- 🟡 [중급] 네트워크 (Lv.3) : 인접 행렬에서의 연결 요소 파악
- 🟡 [중급] 무인도 여행 (Lv.2) : 2D 격자 연결 영역 탐색 및 합산
- 🔴 [고급] 단어 변환 (Lv.3) : 스스로 간선(Edge)을 정의하는 BFS
- 🔴 [고급] 경주로 건설 (Lv.3) : 진입 방향에 따른 3차원 방문 배열 처리
2. ⚙️ 구현 및 시뮬레이션
- 🟢 [초급] 공원 산책 (Lv.1) : 2D 격자 이동 및 예외 처리
- 🟢 [초급] 바탕화면 정리 (Lv.1) : 최소/최대 좌표 추출
- 🟡 [중급] 주차 요금 계산 (Lv.2) : 시간 파싱 및 해시 누적 연산
- 🟡 [중급] 두 큐 합 같게 만들기 (Lv.2) : Queue 순환 로직 및 타입 제어
- 🔴 [고급] 자물쇠와 열쇠 (Lv.3) : 2D 배열 90도 회전 및 패딩(Padding) 기법
- 🔴 [고급] 표 병합 (Lv.3) : 1D/2D 배열 매핑 및 분리 집합(Union-Find)
3. 🗝️ 해시 (Hash) & 투 포인터 (Two Pointers)
- 🟢 [초급] 완주하지 못한 선수 (Lv.1) : HashMap 기본 (
getOrDefault) - 🟢 [초급] 구명보트 (Lv.2) : 배열 정렬 후 양 끝 포인터 접근
- 🟡 [중급] 의상 (Lv.2) : 카테고리 분류 및 조합 계산
- 🟡 [중급] 연속된 부분 수열의 합 (Lv.2) : 슬라이딩 윈도우 (부분합)
- 🔴 [고급] 베스트앨범 (Lv.3) : 다중 해시맵 및 객체 정렬 (
Comparable) - 🔴 [고급] 보석 쇼핑 (Lv.3) : Hash Map + 투 포인터 최단 구간 탐색
4. 🔍 이분 탐색 (Binary Search / Parametric)
- 🟢 [초급] 예산 (Lv.1) : 정렬 후 누적합 탐색
- 🟢 [초급] 순위 검색 (Lv.2) : 파싱 및
lower_bound직접 구현 - 🟡 [중급] 입국심사 (Lv.3) : 파라메트릭 서치 (결정 문제로 치환)
- 🔴 [고급] 징검다리 건너기 (Lv.3) : 이분 탐색 내부 O(N) 슬라이딩 윈도우 검증
5. 🧩 동적 계획법 (Dynamic Programming)
- 🟢 [초급] 피보나치 수 (Lv.2) : 1차원 점화식 및 모듈러 연산
- 🟡 [중급] 정수 삼각형 (Lv.3) : 2D 배열 하향식 누적합
- 🟡 [중급] 등굣길 (Lv.3) : 2D 격자 이동 경로 경우의 수 누적
- 🔴 [고급] N으로 표현 (Lv.3) :
Set컬렉션 배열을 활용한 상태 공간 DP
🚀 Phase 2: 심화 특수 유형 (Big Tech 변별력)
6. 🔄 상태 환원형 백트래킹 & 외판원 순회(TSP)
트랜잭션 롤백처럼, 재귀 탐색 후 변경된 맵의 상태나 방문 기록을 원상 복구하는 기법.
- 🔴 사라지는 발판 (Lv.3) : 상태 환원과 미니맥스(Minimax) 게임 이론의 결합
- 🔴 양과 늑대 (Lv.3) : DFS 트리를 오가며 상태를 복구하는 백트래킹
7. 🧮 비트마스킹 (Bitmasking) 결합
방문 여부(boolean 배열)를 단 하나의 정수(int) 비트 연산으로 압축하여 O(1)로 상태를 관리. 외판원 순회(TSP)의 필수 최적화 기법.
- 🟡 배달 (Lv.2) : 다익스트라 베이스에 비트마스킹 맛보기
- 🔴 외벽 점검 (Lv.3) : 순열 생성 및 비트마스킹을 통한 상태 검사
8. 🗺️ 2차원 누적합 (IMOS 알고리즘)
2D 배열에 다수의 범위 업데이트가 발생할 때, 모서리 마킹 후 단 한 번의 O(N^2) 스위핑으로 결과를 도출.
- 🔴 파괴되지 않은 건물 (Lv.3) : IMOS 알고리즘을 모르면 효율성을 절대 통과할 수 없는 필수 문제
9. 🌳 트라이 (Trie)
문자열 자동완성이나 접두사 검색을 DB 인덱스처럼 극단적으로 빠르게 수행하는 트리 자료구조.
- 🔴 가사 검색 (Lv.4) : 트라이 자료구조의 정석이자 구현 끝판왕
관련 문서
- (Algorithm) 60일 계획 - 핵심 개념 및 특징 정리 — 동일한 코딩테스트 대비 목적의 선행 커리큘럼
- (Algorithm) 순위검색 - 핵심 개념 및 특징 정리 — Phase 1 이분 탐색 초급 문제 상세 풀이
- (Algorithm) 예산 - 핵심 개념 및 특징 정리 — Phase 1 이분 탐색 초급 문제 상세 풀이
- (Algorithm) 타겟넘버 - 핵심 개념 및 특징 정리 — Phase 1 완전 탐색 초급 문제 상세 풀이
- (Algorithm) 네트워크 - 핵심 개념 및 특징 정리 — Phase 1 완전 탐색 중급 문제 상세 풀이
- (Algorithm) 무인도여행 - 핵심 개념 및 특징 정리 — Phase 1 완전 탐색 중급 문제 상세 풀이
- (Algorithm) 단어변환 - 핵심 개념 및 특징 정리 — Phase 1 완전 탐색 고급 문제 상세 풀이
- (Algorithm) 경주로건설 - 핵심 개념 및 특징 정리 — Phase 1 완전 탐색 고급 문제 상세 풀이